On a network of computers such as the Internet, a denial of service (DoS) attack is an incident in which a user or organization is deprived of the services of a resource they would normally expect to have. Typically, the loss of service is the inability of a particular network service, such as e-mail, to be available or the temporary loss of all network connectivity and services. In the worst cases, for example, a Web site accessed by millions of people can occasionally be forced to temporarily cease operation. Although usually intentional and malicious, a DoS attack can sometimes happen accidentally. A DoS attack is a type of security breach to a computer system that does not usually result in the theft of information or other security loss. However, these attacks can cost the victim a great deal of time and money.
In some cases, to find the attacker, an Internet Protocol (IP) traceback path is constructed. The traceback path is the path from the victim's site back to the attacker's site. It is often useful to learn the path that packets take through the network (e.g., Internet) between sites. This is especially important for dealing with certain DoS attacks, where a source IP is forged. There are other uses as well, including path characterization and detection of asymmetric routes. There are existing path tracing tools, such as traceroute. However, the traceroute is initiated at the attacker's site and is therefore useless to the victim's site. When forwarding packets, routers can, with a low probability, generate a traceback message that is sent along to the destination. With enough traceback messages from enough routers along the path, the traffic source and path can be determined. However, traceback generates additional traffic over the network.
One IP traceback technique is called a probabilistic packet marking (PPM) technique. PPM is the process of setting the bits allocated to IP traceback randomly, and then using this to determine the path of attack. The process of using these bits to store a router ID and a hop count is one example of PPM. In a packet-switching network, a hop is the trip a data packet takes from one router or intermediate point to another in the network. On the Internet (or a network that uses TCP/IP), the number of hops a packet has taken toward its destination (called the “hop count”) is kept in the packet header. Every router forwards a packet independently of other routers with some probability, p, that it writes its unique router ID to those bits and sets the hop count to zero. Thus, a probability that the router ID is left unchanged and the hop count is incremented is equal to 1−p. When the attacker is performing a DoS operation on the target system (e.g., victim) by sending a stream of packets along a path, L, if p=(1/L), then after the victim has received L(log(L)) packets, the victim knows the entire traceback path to the attacker.